import java.util.Stack;
import java.util.Vector;

import javax.microedition.lcdui.Display;

import cpagraph.Graph;

/**
 * Class that contains the computing algorithm and works with the graph
 * @author Cem Altel
 * @author Alex Bruck
 * @author Paula Gonz�lez Mu�oz
 */
public class MapEngine
{
	/**
	 * 
	 */
	Map map;
	
	/**
	 * 
	 */
	Graph graph;
	
	/**
	 * 
	 */
	Display display;
	
	/**
	 * 
	 */
	Vector list_stops = null;
	
	/**
	 * 
	 */
	double [][] distances = null;	// feed weights
	
	/**
	 * Constructor
	 * @param map
	 * @param display
	 */
	public MapEngine(Map map, Display display)
	{
		this.map = map;
		this.display = display;
	}
	
	/**
	 * @param origin - Origin node for the computations
	 * @param dest - Destination node for the computations
	 * @return Returns the Vector that contains the route
	 */
	public Vector findRoute(String origin, String dest)
	{
		//boolean pathFound = false;
		Vector result = new Vector();
		// finds a path from origin to dest
		// returns true if a path is found successfully
		// updates the display as necessary
		return result;
	}
	
	public static double computeDistance(double lat1, double lon1, double lat2, double lon2)
	{
		double R = 6371; // earth's radius in km
		double dLat = Math.toRadians(lat2-lat1);
		double dLon = Math.toRadians(lon2-lon1); 
		double a = Math.sin(dLat/2) * Math.sin(dLat/2) +
		        Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2)) * 
		        Math.sin(dLon/2) * Math.sin(dLon/2); 
		double c = 2 * MathUtil.aTan2(Math.sqrt(a), Math.sqrt(1-a)); 
		return R * c;
	}
	
	/**
	 * Algorithm that computes the shortest distance between nodes
	 */
	public void dijkstra()
	{
		boolean [] known = new boolean [list_stops.size()];
		double [] dist = new double [list_stops.size()];
		int [] path = new int [list_stops.size()];
		for (int i=0;i<list_stops.size();i++)
		{
			known[i] = false;
			dist[i] = Double.MAX_VALUE;
			path[i] = -1;			
		}
		dist[0] = 0;
		known[0] = true;
		int current = 0;
		for (;;)
		{
			if (current == -1)
				break;
			known[current] = true;
			for (int i=0;i<list_stops.size();i++)
			{
				if (distances[current][i] <= 0)
					continue;
				if (!known[i])
					if (dist[current] + distances[current][i] < dist[i])
					{
						dist[i] = dist[current] + distances[current][i];
						path[i] = current;
					}
			}
			current = getSmallest(known);
		}
		int [][] allPath = new int [list_stops.size()][list_stops.size()];
		for (int i=0;i<list_stops.size();i++)
			for (int j=0;j<list_stops.size();j++)
				if (j == 0)
					allPath[i][j] = 0;
				else
					allPath[i][j] = -1;
		addAllToPath(path, allPath);
		displayPath(allPath);
	}
	
	/**
	 * helper function for dijkstra(), gets the next edge
	 * @param known identifies which nodes are flagged so far
	 * @return the edge to be investigated at next
	 */
	private int getSmallest(boolean [] known)
	{
		double value = -1;
		int chosen = -1;
		for (int i=0;i<known.length;i++)
		{
			if (!known[i])
				continue;
			for (int j=0;j<known.length;j++)
				if (!known[j] && (value == -1 || (distances[i][j] < value) && distances[i][j] > 0))
				{
					value = distances[i][j];
					chosen = j;
				}
		}
		return chosen;
	}
	
	/**
	 * helper function for dijkstra(), constructs individual paths
	 * @param pathnum path information specific to dijkstra's algorithm
	 * @param allPath the output containing all paths
	 */
	private void addAllToPath(int [] pathnum, int [][] allPath)
	{
		for (int i=1;i<allPath.length;i++)
		{
			Stack st = new Stack();
			Integer node = new Integer(pathnum[i]);
			st.push(new Integer(i));
			while (node.intValue() != 0)
			{
				st.push(node);
				node = new Integer(pathnum[node.intValue()]);
			}
			while (!st.isEmpty())
				addToPath(allPath[i], ((Integer)st.pop()).intValue());
		}
	}
	
	/**
	 * adds a node to the end of the list
	 * @param path list containing the nodes taken so far
	 * @param way the new element to be inserted
	 */
	private void addToPath(int [] path, int way)
	{
		for (int i=0;i<path.length;i++)
			if (path[i] == -1)
			{
				path[i] = way;
				break;
			}
	}
	
	/**
	 * Displays all the paths and their total lengths
	 * @param path information about the actual paths
	 */
	public void displayPath(int [][] path)
	{
		for (int i=0;i<path.length;i++)
		{
			System.out.print(list_stops.elementAt(0) + " - " + list_stops.elementAt(i) + ": ");
			for (int j=0;j<path[i].length;j++)
			{
				if (path[i][j] == -1)
					break;
				System.out.print(list_stops.elementAt(path[i][j]) + " ");
			}
			System.out.println();
			System.out.println("total: " + computePath(path[i], distances));
		}
	}
	
	/**
	 * computes the total length of a path
	 * @param path the path whose length is to be computed
	 * @param distances information about the edges
	 * @return total length of the path
	 */
	private int computePath(int [] path, double [][] distances)
	{
		int sum = 0;
		for (int i=0;i<path.length-1;i++)
		{
			if (path[i+1] == -1)
				break;
			sum += distances[path[i]][path[i+1]];
		}
		return sum;
	}
}